home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / tsql / doc / tsql.mail / 000114_csj@iesd.auc.dk _Tue May 11 01:12:15 1993.msg < prev    next >
Internet Message Format  |  1996-01-31  |  36KB
  1. Received: from iesd.auc.dk by optima.CS.Arizona.EDU (5.65c/15) via SMTP
  2.     id AA01763; Mon, 10 May 1993 16:14:43 MST
  3. Received: from yellow.iesd.auc.dk by iesd.auc.dk with SMTP id AA02425
  4.   (5.65c8/IDA-1.5/MD for <tsql@cs.arizona.edu>); Tue, 11 May 1993 01:12:15 +0200
  5. Date: Tue, 11 May 1993 01:12:15 +0200
  6. From: "Christian S. Jensen" <csj@iesd.auc.dk>
  7. Message-Id: <199305102312.AA02425@iesd.auc.dk>
  8. To: tsql@cs.arizona.edu
  9. Subject: TSQL Benchmark document (Latex).
  10.  
  11. %\documentstyle[twocolumn]{article}
  12. \documentstyle[11pt]{article}
  13. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  14. % This paper is intended to evolve into the first version of the TSQL
  15. % benchmark. For this version of the benchmark, this document contains
  16. % the final database (schema and instance) and taxonomy of queries.
  17. %
  18. % To complete the benchmark, benchmark queries must be added (Task 4
  19. % of the TSQL Benchmark Initiative).
  20. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  21.  
  22. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  23. % VARIOUS MACROS
  24. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  25.  
  26. \long\def\comment#1{}
  27.  
  28. \comment{For twocolumn style:
  29. \setlength{\textheight}{8.85in}%8.75in}
  30. \setlength{\columnsep}{2.0pc}
  31. \setlength{\textwidth}{6.8in}
  32. \setlength{\footheight}{0.0in}
  33. \setlength{\topmargin}{0.0in}%{0.25in}
  34. \setlength{\headheight}{0.0in}
  35. \setlength{\headsep}{0.0in}
  36. \setlength{\oddsidemargin}{-.19in}
  37. \setlength{\parindent}{1pc}}
  38.  
  39. \addtolength{\textwidth}{1.485in}%{1.2in}
  40. \setlength{\oddsidemargin}{.1in}%{.3in}
  41. \setlength{\evensidemargin}{.1in}%{.3in}
  42. \addtolength{\topmargin}{-.85in} %{-1.35in}
  43. \addtolength{\textheight}{1.8in} %{2.8in}
  44.  
  45. \newenvironment{BNF}{\vspace{-\partopsep}\addtolength{\baselineskip}{+4pt}
  46. \samepage\begin{tabbing}
  47. %\quad
  48. \ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=
  49. \+\kill}{\end{tabbing}\vspace{-\partopsep}\vspace{-\topsep}\vspace{-\parsep}}
  50.  
  51. % => in roman
  52. \def\arrow{\char'75\char'76\relax}
  53. % ::= in roman
  54. \def\is{{\rm \verb.:.\verb.:.\char'75\relax}}
  55. % { in roman
  56. \def\lbr{$\bigl\{$}
  57. % } in roman
  58. \def\rbr{$\bigr\}\;$}
  59. % }* in roman
  60. \def\starbr{$\bigl\}${\rm *}$\;$}
  61. % }? in roman
  62. \def\quesbr{$\bigr\}{}^?$}
  63. % }+ in roman
  64. \def\plusbr{$\bigr\}{}^+$}
  65. % | in roman
  66. \def\vbar{$\bigl|\;$}
  67. % 'chars 
  68. \def\qt#1{`{#1}'}
  69. % nonterminals (arg is the name)
  70. \def\nt#1{$<${\rm #1}$>$}
  71. %typerwriter font
  72. \def\ttt#1{{\tt #1}}
  73. %comment
  74. \def\com#1{{\tt /$\ast$} {\footnotesize #1}}
  75.  
  76. %double square brackets
  77. \def\dsl{{\tt [\hspace{-4.5pt}[ \hspace{-1pt}}}
  78. \def\dsr{{\tt ]\hspace{-4.5pt}]}}
  79. \def\dsrs{{\tt ]\hspace{-4.5pt}]\hspace{4pt}}}
  80.  
  81. \newenvironment{prog} { \begin{center} \begin{minipage}{3in}
  82. \begin{tabbing} nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=\kill
  83. }{\end{tabbing} \end{minipage} \end{center}}
  84.  
  85. \newcommand{\mvd}{\mbox{$\rightarrow \!\!\! \rightarrow \;$}}
  86. \newcommand{\autsp}{$\;\;\;$}
  87.  
  88. \long\def\query#1#2#3{\begin{verse} {\bf Query \no} {#1} \end{verse} \begin{verse} {\bf Answer:} {#2} \end{verse} \begin{verse} {\bf Category:} {#3} \end{verse}}
  89.  
  90. \newcounter{qnumber}
  91. \newcounter{rnumber}[subsection]
  92. \newcounter{gnumber}[subsubsection]
  93. \newcommand{\no}{\setcounter{qnumber}{\value{subsection}} \setcounter{rnumber}{\value{subsubsection}}\protect\refstepcounter{gnumber} Q \protect\theqnumber.\protect\thernumber.\protect\thegnumber:}
  94.  
  95. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  96. % PAPER START
  97. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  98.  
  99. \begin{document}
  100.  
  101. \title{\Large\bf The TSQL Benchmark \\ DRAFT}
  102.  
  103. \author{James Clifford \autsp Shashi K.~Gadia \autsp Fabio Grandi
  104.   \autsp Christian S.~Jensen \\ Patrick Kalua \autsp Sunil Nair \autsp
  105.   Edward Robertson \autsp John F.~Roddick \\ Maria Rita Scalas \autsp
  106.   Richard T.~Snodgrass \autsp Abdullah Tansel \autsp Paolo Tiberio \\ 
  107.   Alexander Tuzhilin \autsp Gene Wuu}
  108.  
  109. %Note that the list of authors is preliminary and may not be accurate!
  110.  
  111. \date{May 8, 1993} 
  112. \maketitle
  113.  
  114. \section{Introduction}
  115.  
  116. \subsection{Goal}
  117.  
  118. The central goal of this document is to provide the temporal database
  119. community with a {\em comprehensive consensus benchmark} for temporal
  120. query languages that is {\em independent} of any existing language
  121. proposal.
  122.  
  123. This is not a performance benchmark, but is rather a {\em semantic}
  124. benchmark intended to be an aid in evaluating the user-friendliness of
  125. proposals for temporal query languages. Thus, temporal query languages
  126. should ideally be able to express the benchmark queries both
  127. conveniently and naturally.
  128.  
  129. To obtain a consensus benchmark, researchers in temporal databases
  130. have been invited to participate in this initiative, and each researcher
  131. that has contributed significantly will be a coauthor. The electronic
  132. mail distribution {\tt tsql@cs.arizona.edu} is used as the medium for
  133. discussing the benchmark and related issues.
  134.  
  135. As a consequence of the central goal above, no existing temporal data
  136. models are used or mentioned. The relation schemas of the benchmark
  137. are expressed as sets of attributes, including one attribute
  138. illustrating user-defined time. However, the underlying temporal
  139. aspects are implicit (of course, specific temporal data models might
  140. add explicit temporal attributes). The contents of the relations are
  141. described in natural language. The benchmark queries are also given
  142. only in natural language.
  143.  
  144. The benchmark is {\em not} intended to constitute a metric for query
  145. language completeness, and as such it is not a substitute for a
  146. rigorous {\em theoretical} study of expressive powers of various
  147. temporal query languages. Comprehensiveness of the benchmark is
  148. desirable only to ensure that all aspects of query language design are
  149. covered.
  150.  
  151. It it emphasized that using the benchmark as an advanced, quantitative
  152. scoring system for comparing languages makes little sense. Thus, one
  153. language is not necessarily superior to another just because one is
  154. capable of expressing more benchmark queries than the other. Rather,
  155. the focus is on user-friendliness.
  156.  
  157. \subsection{Scope}
  158.  
  159. Within certain boundaries, discussed next, the benchmark is intended
  160. to contain all queries that appear reasonable and that are consistent
  161. with the schema and data of the benchmark.
  162.  
  163. First, the benchmark is of a semantic nature---in its current form, it
  164. is not aimed at performance comparisons. The intention is to provide a
  165. foundation for comparing the descriptive and operational
  166. characteristics and capabilities of temporal query languages, not
  167. their performance characteristics. Properly extended with additional
  168. relation schemas and a variety of large instances, the benchmark can
  169. also be used for performance comparisons.
  170.  
  171. Second, a number of restrictions are imposed on which types of queries
  172. are admissible in this version of the benchmark, including the
  173. following.
  174.  
  175. \begin{itemize}
  176. \item Queries are restricted to valid time only. Transaction-time
  177.   related queries are not explored.
  178.  
  179. \item Schema evolution and versioning are not considered.
  180.  
  181. \item Incompleteness is not considered. 
  182.  
  183. \item Recursive queries are not included.
  184.  
  185. \item General temporal reasoning is beyond the scope of this version
  186.   of the benchmark.
  187.  
  188. \item Queries involving aggregation facilities are not considered.
  189.  
  190. \item Only queries are included---updates are not considered.
  191.  
  192. \item Continuous attributes such as time are not included.
  193.  
  194. \item The querying of data valid in the future is not explored.
  195.  
  196. \comment{
  197. \item Queries involving relations with multivalued dependencies (in
  198.   the snapshot sense) are not explored.}
  199.  
  200. \comment{
  201. \item User-defined time, including the interaction between
  202.   user-defined time and valid time, is not considered.}
  203.  
  204. \comment{
  205. \item Queries involving complex data retrieval are excluded.}
  206.  
  207. \comment{
  208. \item Inheritance at both the schema and data levels is not
  209.   considered.}
  210.  
  211. \comment{
  212. \item Nested queries are not included.}
  213.  
  214. \comment{
  215. \item For simplicity, each relation is used only once in each query.}
  216.  
  217. \end{itemize}
  218.  
  219. These advanced aspects are excluded solely for pragmatic reasons, and
  220. the exclusion is not meant to imply in any way that the aspects are
  221. not important. The restrictions simply represent an attempt to reduce
  222. the size of the initial benchmark to manageable proportions.
  223.  
  224. It is emphasized that this benchmark is merely the first in a sequence
  225. of ever-more comprehensive benchmarks. Later benchmarks will relax the
  226. above restrictions on the scope of comprehensiveness imposed on this
  227. benchmark. Specifically, the next version of the benchmark is intended
  228. to include queries that involve aggregation.
  229.  
  230. \comment{
  231. Specifically, the next version of the benchmark is intended to include
  232. queries that use the same relation more than once, utilize
  233. aggregation, and involve both valid time and user-defined time.}
  234.  
  235. \section{The Benchmark Database Schema}
  236.  
  237. \subsection{Criteria}
  238.  
  239. A suitable database schema for the benchmark should satisfy four
  240. criteria.
  241.  
  242. \begin{itemize}
  243. \item{} The schema should be natural. That is, it should correspond to
  244.   a reasonable, though possibly greatly simplified, segment of the
  245.   real world. This both reduces the need to explain the model and
  246.   enhances the ability to recognize verball pitfalls in the path to
  247.   the query instances.
  248.  
  249. \item{} The schema should be simple. This will aid in making the
  250.   benchmark easy to understand. This criterion restricts the number of
  251.   relation schemas and the number of attributes of the individual
  252.   schemas. Additionally, the names of the relations and of the
  253.   attributes should be short, as they will be referenced repeatedly.
  254.  
  255.   When an extension is proposed, the benefits should be carefully
  256.   compared with the added complexity.
  257.  
  258. \item{} The schema should allow for comprehensiveness within the
  259.   chosen scope. Using the schema, it should be possible formulate
  260.   queries of all the types that appear reasonable.
  261.  
  262.   This indicates a need for at least two related relation schemas (for
  263.   natural join queries).
  264.  
  265. \item{} A schema that has already been used frequently is preferred
  266.   over a new schema. This guarantees that many existing queries can be
  267.   adapted easily to the benchmark.
  268.  
  269. \item{} For clarity, schema and attribute names must start with
  270.   capital letters.
  271. \end{itemize}
  272.  
  273. \subsection{The Schema}
  274.  
  275. The database schema consists of three valid-time relation schemas,
  276. {\tt Emp}, {\tt Skills}, and {\tt Dept}. They are defined as follows.
  277.  
  278. Relation {\tt Emp} uses the attributes {\tt Name}, {\tt Salary}, and
  279. {\tt Dept} for recording the salaries of employees and the departments
  280. where they work. In addition, it contains attributes {\tt Gender} and
  281. {\tt D-birth} which indicate the gender and date of birth of an
  282. employee. While the salary and department of an employee varies over
  283. time, both {\tt Gender} and {\tt D-birth} are time-invariant.
  284.  
  285. Relation {\tt Skills} records the association of employees with skills
  286. via the two attributes {\tt Name} and {\tt Skill}. The skills of an
  287. employee may vary over time. For example, employees are considered to
  288. have the skill ``driving'' only during those interval(s) when they
  289. hold valid licenses.
  290.  
  291. Relation {\tt Dept} records the association of employees, as managers,
  292. with departments, and it contains three attributes, {\tt Department},
  293. recording a department name, {\tt Manager}, recording the manager of
  294. the department, and {\tt Budget}, recording the budget of the
  295. department.
  296.  
  297. Attributes {\tt Name}, {\tt Dept}, {\tt Department}, {\tt Skill}, and
  298. {\tt Manager} are of type {\tt textString}; attribute {\tt Gender} is
  299. one of {\tt F} (female) and {\tt M} (male); {\tt Salary} and {\tt
  300.   Budget} are of type {\tt integer}; and {\tt D-birth} is a
  301. user-defined time value which may be compared with valid times.
  302.  
  303. The relation schemas obey the following {\em snapshot} functional
  304. and multivalued dependencies:
  305.  
  306. \begin{prog}
  307. For {\tt Emp}: \\
  308. \> {\tt Name} $\rightarrow$ {\tt Salary} \\
  309. \> {\tt Name} $\rightarrow$ {\tt Dept} \\
  310. \> {\tt Name} $\rightarrow$ {\tt Gender} \\
  311. \> {\tt Name} $\rightarrow$ {\tt D-birth} \\
  312. For {\tt Skills}: \\
  313. \> {\tt Name} $\mvd$ {\tt Skill} (and {\tt Name} $\not\rightarrow$
  314. {\tt Skills}) \\
  315. For {\tt Dept}: \\
  316. \> {\tt Department} $\rightarrow$ {\tt Manager} \\
  317. \> {\tt Manager} $\rightarrow$ {\tt Department} \\
  318. \> {\tt Department} $\rightarrow$ {\tt Budget}
  319. \end{prog}
  320.  
  321. Note that {\tt Name} is the primary key of {\tt Emp} (it is the only
  322. candidate key). For {\tt Skills}, there is no non-trivial key. For
  323. {\tt Dept}, each of {\tt Department} and {\tt Manager} is a candidate
  324. key, and {\tt Department} is selected as the primark key.
  325.  
  326. Each of the relation schemas are in snapshot Boyce-Codd normal form.
  327.  
  328. It is emphasized that the notion of key does not capture
  329. correspondence between attribute values and the real-world objects
  330. they represent. As one consequence, it is possible in this schema,
  331. e.g., for a person to change {\tt Name} attribute value over time.
  332.  
  333. The attribute {\tt Manager} of {\tt Dept} is a foreign key for the
  334. attribute {\tt Name} of {\tt Emp}. Thus, a tuple is allowed to exist
  335. in the {\tt Dept} relation only if, for each non-empty snapshots of
  336. this tuple, the {\tt Manager} attribute value exists as a {\tt Name}
  337. value of some tuple in the simultaneous snapshot of the {\tt Emp}
  338. relation.
  339.  
  340. \section{The Benchmark Data}
  341.  
  342. \subsection{Criteria}
  343.  
  344. \begin{itemize}
  345. \item{} For clarity, the database instance should ideally accord with
  346.   {\em all and only} those constraints which are explicitly stated in
  347.   the definition of the database schema. 
  348.  
  349. \item{} For simplicity and ease of typing, attribute values should be
  350.   short and salary values should be multiples of \$10,000.
  351.  
  352. \item{} Transitions (i.e., timestamp values) occur only at the
  353.   beginning of the month, and all dates should be in the time interval
  354.   from 1/1/81 to 12/31/88 (because the digits 8 and 9 are relatively
  355.   hard to distinguish). Time intervals are all specified by the
  356.   inclusive starting and ending events. Also for clarity, relation
  357.   instance names should start with lowercase letters.
  358.  
  359. \item{} The data should include a ``hole in the history'' of some
  360.   entity. For example, the database may be designed to contain a whole
  361.   in the employment of some employee.
  362.  
  363. \item{} The data should include asynchronous behavior of attributes.
  364.   For example, the department and salary of employees may change
  365.   independently.
  366. \end{itemize}
  367.  
  368. \subsection{The Proposed Data}
  369.  
  370. Three instances, {\tt emp}, {\tt skills}, and {\tt dept}, are defined
  371. over the {\tt Emp}, {\tt Skills}, and {\tt Dept} relation schemas,
  372. respectively. The contents of these instances is described below.
  373.  
  374. There are two employees, identified by {\em ED\/} and {\em DI\/} in
  375. the following.
  376.  
  377. {\em ED\/} worked in the Toy department from 2/1/82 to 1/31/87, and in
  378. the Book department from 4/1/87 to the present. His name was Ed from
  379. 2/1/82 to 12/31/87, and Edward from 1/1/88 to the present. His salary
  380. was \$20K from 2/1/82 to 5/31/82, then \$30K from 6/1/82 to 1/31/85,
  381. then \$40K from 2/1/85 to 1/31/87 and 4/1/87 to the present. {\em
  382.   ED\/} is male and was born on 7/1/55. Several skills are recorded
  383. for {\em ED\/}. He has been qualified for typing since 4/1/82 and
  384. qualified for filing since 1/1/85. He was qualified for driving from
  385. 1/1/82 to 5/1/82 and from 6/1/84 to 5/31/88.
  386.  
  387. {\em DI\/} worked in and managed the Toy department from 1/1/82 to the
  388. present. Her name is Di throughout her employment. The budget of the
  389. Toy department was \$150K from 1/1/82 to 7/31/84, \$200K from 8/1/84
  390. to 12/31/86, and \$100K from 1/1/87 to the present. Her salary was
  391. \$30K from 1/1/82 to 7/31/84, \$40K from 8/1/84 to 8/31/86, then \$50K
  392. from 9/1/86 to the present. {\em DI\/} is female and was born on
  393. 10/1/60. {\em DI\/} has been qualified for directing from 1/1/82 to
  394. the present.
  395.  
  396. The present time (i.e., the value of {\tt now}) is 1/1/90.
  397.  
  398. \section{Classification of Benchmark Queries}
  399.  
  400. A classification of benchmark queries will be based on a comprehensive
  401. taxonomy of queries. First, critria for such a taxonomy are outlined.
  402. Next, the taxonomy itself is presented. As the taxonomy is too
  403. fine-grained, categories are then merged into an adequate number of
  404. groups which can subsequently be used for classification.
  405.  
  406. \subsection{Criteria}
  407.  
  408. Three criteria for an appropriate taxonomy of benchmark queries are
  409. suggested.
  410. \begin{itemize}
  411. \item{} The taxonomy should be schema and instance independent. This
  412.   criterion helps ensure that the taxonomy will persist when the
  413.   benchmark database schema evolves as new versions appear. Ideally,
  414.   this will allow for an incremental mode of work, where only new
  415.   queries need to be categorized and existing queries do not need
  416.   re-categorization.
  417. \item{} The taxonomy should provide comprehensive coverage of
  418.   benchmark queries. Comprehensiveness is desirable to avoid holes and
  419.   point to many categories of queries.
  420. \item{} The taxonomy should be useful when structuring the
  421.   presentation of benchmark queries. Most importantly, it should
  422.   provide sufficient structure. Thus, taxonomies that have only few
  423.   categories and that map many queries to single categories are
  424.   problematic. If the number of categories is excessive for
  425.   presentation purposes, classes of categories may be identified with
  426.   individual sections.
  427. \end{itemize}
  428.  
  429. \subsection{The Taxonomy}
  430.  
  431. The taxonomy is characterized as having a projection (output) and a
  432. selection component, much like SQL. Then each component is covered in
  433. turn. Finally, the full taxonomy is summarized and a notation for
  434. naming individual categories is defined.
  435.  
  436. \subsubsection{Top-level Taxonomy}
  437.  
  438. At the top level, the taxonomy is divided into two orthogonal parts,
  439. namely a part where queries are categorized according to their {\em
  440.   output component} and a part where the categorization is based on
  441. the {\em selection component}. Thus, a category is described by two
  442. components, as illustrated in Figure~\ref{fig:top}.
  443.  
  444. \begin{figure}[htbp] {\small
  445.   \[
  446.     \{ <\mbox{output component}> \}
  447.     \times 
  448.     \{ <\mbox{selection component}> \}
  449.   \]}
  450.   \caption{Top-level Description of Benchmark Taxonomy}
  451.   \label{fig:top}
  452. \end{figure}
  453.  
  454. This top-level design reflects the SQL template (i.e., {\tt SELECT}
  455. \ldots {\tt FROM} \ldots {\tt WHERE} \ldots). The first component
  456. categorizes the contents of the {\tt SELECT} clause, and the second
  457. component categorizes the contents of the {\tt WHERE} clause. No
  458. component is needed to reflect the {\tt FROM} clause where tuple
  459. variables are defined. The two components are orthogonal only in the
  460. same sense that the {\tt WHERE} and {\tt SELECT} clauses of a
  461. particular query are orthogonal.
  462.  
  463. \subsubsection{Output-based Taxonomy}
  464.  
  465. The output-based taxonomy is intended to reflect the part of queries
  466. where the format of the resulting tuples is specified. The taxonomy is
  467. described in Figure~\ref{fig:pro1} and is explained in the following.
  468.  
  469. \begin{figure*}[htbp]
  470. \begin{center}
  471.   \leavevmode
  472.     \[
  473.       \left\{ \begin{array}{c}
  474.         \mbox{\underline{explicit-attribute component}} \\
  475.         \mbox{none} \\
  476.         \mbox{projected} \\
  477.         \mbox{complete}
  478.       \end{array} \right\}
  479.       \times
  480.       \left\{ \begin{array}{c}
  481.         \mbox{\underline{valid-time component}} \\
  482.         \mbox{none} \\
  483.         \left\{ \begin{array}{c}
  484.           \mbox{\underline{type}} \\
  485.           \mbox{event} \\
  486.           \mbox{interval} \\
  487.           \mbox{element}
  488.         \end{array} \right\}
  489.         \times
  490.         \left\{ \begin{array}{c}
  491.           \mbox{\underline{value}} \\
  492.           \mbox{derived} \\
  493.           \mbox{imposed}
  494.         \end{array} \right\}
  495.       \end{array} \right\}
  496.     \]
  497. \end{center}
  498. \caption{Output-based Taxonomy}
  499. \label{fig:pro1}
  500. \end{figure*}                                                       
  501.  
  502. The idea is to distinguish between queries based on the format of the
  503. result tuples. A tuple may include an explicit-attribute component and
  504. a valid-time component, each of which are considered next.
  505.  
  506. If present, the explicit-attribute component, may contain all
  507. attributes in the argument relation (multiple relations are discussed
  508. below) or it may contain a subset of the attributes in the argument
  509. relation. In the first case, the explicit attribute component is
  510. ``complete,'' and in the second, it is ``projected.''
  511.  
  512. To exemplify, consider a tuple telling that Ed is in the Book
  513. department from 1/1/82 to 12/31/84. Here ``Ed'' and ``Book''
  514. constitute the explicit-attribute component, and ``1/1/82'' and
  515. ``12/31/84'' is the valid-time component. If the argument relation
  516. contained an attribute ``Salary'' in addition to the Name and
  517. Department attributes, this result is projected.
  518.  
  519. If several relations are used in a query, the argument relation is the
  520. Cartesian product of these, i.e., the schema is the concatenation of
  521. the schemas of the relations used in the query.
  522.  
  523. The valid-time component of a tuple may be of three types. First, it
  524. may be an event, i.e., a single time value (e.g., 3/1/83). Second, it
  525. may be an interval, i.e., a sequence of consecutive time values (e.g.,
  526. as above). Third, it may be an element, i.e., a set of time values
  527. which may be described by a set of intervals (e.g., 1/1/82 to
  528. 12/31/84, 2/1/85 to 3/31/85, and 5/1/86 to 5/31/86).
  529.  
  530. Orthogonally, the value of a valid-time component may be derived or
  531. imposed. A derived value is computed solely in terms of the valid-time
  532. components of the tuples in the argument relation. An imposed value is
  533. computed by explicit assignment in the query.
  534.  
  535. Note that at least one of the two components must be present in the
  536. result of a query. This part of the taxonomy results in 20 mutually
  537. exclusive categories.
  538.  
  539. The distinctions above are based on the schema of result relations. It
  540. is possible also to distinguish between the cardinalities of result
  541. relations, e.g., between set-valued and single-tuple valued results.
  542.  
  543. \subsubsection{Selection-based Taxonomy}
  544.  
  545. The selection component is divided into two parts, one for valid-time
  546. selection and one for selection not involving valid time. See
  547. Figure~\ref{fig:selt}.
  548.  
  549. \begin{figure}[htbp] {\small
  550.   \[
  551.     \{ <\mbox{valid-time selection}> \}^\ast
  552.     \times 
  553.     \{ <\mbox{non-temporal selection}> \}^\ast
  554.   \]}
  555.   \caption{Top-level Selection-based Taxonomy}
  556.   \label{fig:selt}
  557. \end{figure}
  558.  
  559. Both parts are based on the same observation. In general, a selection
  560. predicate is built from atomic selection predicates using logical
  561. operators (e.g., {\tt and}, {\tt or}, and {\tt implies}) and
  562. parenthesis. Both parts categorize queries based on the atomic
  563. predicates used in the queries. As several types of atomic predicates
  564. may be used in the same query, queries generally fall into multiple
  565. categories (as indicated in Figure~\ref{fig:selt} by the Kleene star,
  566. ``${}^\ast$''). We examine each part of the selection-based taxonomy
  567. in turn.
  568.  
  569. Atomic valid-time selection predicates are assumed to be of the form
  570. \[ arg_1 \mbox{\tt ~op~} arg_2 \hspace*{2mm},\]
  571. where {\tt op} is a some comparison operator (e.g., {\tt precedes}, and
  572. {\tt contains}). It is assumed that $arg_1$ is the valid time of the
  573. data, and restrictions are imposed based on the type of the comparison
  574. operator, on the origin of $arg_2$, and on the type of $arg_2$.
  575. Figure~\ref{fig:sel2} outlines the categories.
  576.  
  577. \begin{figure*}[htbp]
  578.   \begin{center}
  579.     \leavevmode
  580.       \[
  581.         \left\{ \begin{array}{c}
  582.           \mbox{\underline{type of comparison operator}} \\
  583.           \mbox{duration-based} \\
  584.           \mbox{ordering-based} \\
  585.           \mbox{containment-based}
  586.         \end{array} \right\}
  587.         \times
  588.         \left\{ \begin{array}{c}
  589.           \mbox{\underline{type of $arg_2$}} \\
  590.           \mbox{event} \\
  591.           \mbox{interval} \\
  592.           \mbox{element}
  593.         \end{array} \right\}
  594.         \times
  595.         \left\{ \begin{array}{c}
  596.           \mbox{\underline{origin of $arg_2$}} \\
  597.           \mbox{explicitly supplied in query} \\
  598.           \mbox{user-defined attribute value} \\
  599.           \mbox{computed from other valid times}
  600.         \end{array} \right\}
  601.       \]
  602.   \end{center}
  603.   \caption{Valid-time Selection-based Taxonomy}
  604.   \label{fig:sel2}
  605. \end{figure*}
  606.  
  607. Three types of comparison operators are identified. First, a
  608. comparison operator may be duration-based. For example the operator
  609. {\tt spanExceeds} returns true if the duration of the first argument
  610. is equal to or larger than the duration of the second argument.
  611. Second, comparison operators may be based on ordering. Operators in
  612. this category include {\tt precedes} and {\tt meets}. The first
  613. applies to all timestamps and evalutes to true if the largest time in
  614. the first argument is smaller than the smallest times in the second
  615. argument. Operator {\tt meets} appears to be useful only for events
  616. and intervals. Two timestamps meet if they are not separated by any
  617. event (i.e., may be coalesced). Operators based on containment include
  618. {\tt =} (identity), {\tt overlaps}, and {\tt contains}.
  619.  
  620. The second argument ($arg_2$) may be an event, an interval, or an
  621. element. Also, it may come from three sources. First, it may be
  622. supplied directly in the query, as a constant. Second, it may be the
  623. value of a user-defined time attribute in an argument tuple. Note that
  624. this is only possible for events if first normal form is required.
  625. Third, like the first argument, the second argument may be computed
  626. from valid times in the argument tuples.
  627.  
  628. If the three types of categories are completely orthogonal, this
  629. part of the taxonomy will contribute with a total of 27 categories.
  630. However, it may be debated whether intervals and elements may be used
  631. as values of user-defined attributes (resulting in non-1NF relations).
  632.  
  633. The final part of the selection-based taxonomy categorizes queries
  634. based solely on the part of the selection component that involves only
  635. ordinary, non-temporal selection.
  636.  
  637. Many possibilities for categorization exist. Below, in
  638. Figure~\ref{fig:sel1}, we distinguish between four significant types
  639. of atomic selection predicates. First, an attribute may be compared
  640. with a constant, supplied by the user. Second, attribute values, both
  641. in the same relation, may be compared. Third, a primary key value may
  642. be compared with a matching foreign key value. Fourth, arbitrary
  643. attributes of possibly distinct relations may be compared. In the
  644. figure, $\theta ::= \; < | > | \leq | \geq | = \;$, i.e., a
  645. combination of equality and/or the one of the two inequality
  646. operators. If we distinguish between situations where only equality is
  647. involved and situations where inequality is involved, this give 8
  648. categories.
  649.  
  650. \begin{figure*}[htbp]
  651.   \begin{center}
  652.     \leavevmode
  653.       \[
  654.         \left\{ \begin{array}{c}
  655.           \mbox{\underline{non-temporal attribute value selection}} \\
  656.           att~\theta~\mbox{\em Constant} \\
  657.           att_1~\theta~att_2 \\
  658.           att_k~\theta~att_{fk} \\
  659.           att(rel_1)~\theta~att(rel_2)
  660.         \end{array} \right\}
  661.         \times
  662.         \left\{ \begin{array}{c}
  663.           \mbox{\underline{comparison operator, $\theta$}} \\
  664.           \mbox{only equality } (=) \\
  665.           \mbox{inequality } (<>)
  666.         \end{array} \right\}
  667.       \]
  668.   \end{center}
  669.   \caption{Non-temporal Selection-based Taxonomy}
  670.   \label{fig:sel1}
  671. \end{figure*}
  672.  
  673. \subsubsection{Additional Contributions---TEMPORARY}
  674.  
  675. The distinction between grouped and ungrouped queries has not been
  676. integrated into the taxonomy. To do that, definitions of these
  677. categories are needed.
  678.  
  679. \subsection{Overview and Naming of Categories}
  680.  
  681. Each query has a single output component, zero or more valid-time
  682. selection components (one per such operator), and zero or more
  683. non-temporal selection-based components (one per such operator). The
  684. taxonomy is summarized in Figure~\ref{fig:tax}. There, the names
  685. introduced in the taxonomy are used along with punctuation in order to
  686. name a category.
  687.  
  688. \begin{figure*}[htbp]
  689. \begin{BNF}
  690. \nt{non-t selection} \=\is\ \= \kill
  691. \nt{category} \> \is \> \nt{output} \qt{/} \lbr \nt{v-t selection}
  692. \starbr \qt{/} \lbr \nt{non-t selection} \starbr \\
  693. \nt{output} \> \is \> \qt{(} \= \lbr None \vbar Projected \vbar
  694. Complete \rbr \qt{,} \` \com{explicit-attribute component} \\
  695. \>\>\> \lbr \= None \vbar \` \com{no valid-time attribute} \\
  696. \>\>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
  697. \com{type of valid-time attribute} \\
  698. \>\>\>\> \lbr Derived \vbar Imposed \rbr \rbr \qt{)} \` \com{value of
  699. valid-time attribute} \\
  700. \nt{v-t selection} \> \is \> \qt{(} \lbr Duration \vbar Ordering \vbar
  701. Containment \rbr \qt{,} \` \com{operator type}\\
  702. \>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
  703. \com{argument type} \\
  704. \>\>\> \lbr Explicit \vbar User-defined \vbar Computed \rbr \qt{)} \`
  705. \com{argument origin} \\
  706. \nt{non-t selection} \> \is \> \qt{(} \lbr \qt{=} \vbar \qt{$<>$} \rbr
  707. \qt{,} \` \com{operator type} \\
  708. \>\>\> \lbr Constant \vbar Single \vbar Foreign \vbar Arbitrary \rbr
  709. \qt{)} \` \com{argument types} \\
  710. \end{BNF}
  711.   \caption{Overview of the Taxonomy used for Naming Categories}
  712.   \label{fig:tax}
  713. \end{figure*}
  714.  
  715. To exemplify the use of Figure~\ref{fig:tax} for naming categories,
  716. consider the query ``When was Ed Manager of the Toy Department.''
  717. This query is in the category shown next (with no valid-time
  718. selection).
  719.  
  720. \begin{center}
  721.   (None, Element, Derived) // (=, Constant)
  722. \end{center}
  723.  
  724. It may be observed that the taxonomy gives rise to a large number of
  725. categories. For example, assuming a single non-temporal operator and no
  726. valid-time operators, there are $20 \times 8 = 160$ categories. Adding
  727. a single valid-time operator while assuming orthogonality yields an
  728. additional 4320 categories!
  729.  
  730. As a result, it becomes necessary to create classes of categories
  731. which then may be used for clasifying the benchmark queries.
  732.  
  733. One approach would be to name a {\em class} of categories of queries,
  734. by simply replacing one or more of the entries with the Kleene star
  735. (``*''), e.g.,
  736.  
  737. \begin{center}
  738. (None, Element, Derived) / (*,*,*) / (=, Constant)
  739. \end{center}
  740.  
  741. The above query category would be in this class. In the next section,
  742. we define the classes to be used in the benchmark.
  743.  
  744. \subsection{Forming Classes from Categories}
  745.  
  746. The idea is to remove distinctions from the comprehensive taxonomy
  747. until a suitable number of classes is obtained. Figure~\ref{fig:tax2}
  748. is thus a reduced version of Figure~\ref{fig:tax}.
  749.  
  750. \begin{figure*}[htbp]
  751. \begin{BNF}
  752. \nt{reduced v-t selection} \=\is\ \= \kill
  753. \nt{class-name} \> \is \> \nt{reduced output} \qt{/} \lbr
  754. \nt{reduced v-t selection} \starbr \\
  755. \nt{reduced output} \> \is \> \qt{(} \= \lbr None \vbar Proj/Comp
  756. \rbr \qt{,} \` \com{explicit-attribute component} \\
  757. \>\>\> \lbr None \vbar Not empty \rbr \qt{)} \qt{/} \` \com{valid-time
  758.   attribute component} \\
  759. \nt{reduced v-t selection} \> \is \> \qt{(} \> \lbr Duration
  760. \vbar Other \rbr \qt{,} \` \com{comparison operator type} \\
  761. \>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
  762. \com{argument type} \\
  763. \>\>\> \lbr Computed \vbar Other \rbr \qt{)} \`
  764. \com{argument origin} 
  765. \end{BNF}
  766.   \caption{Overview of the Classification of Queries}
  767.   \label{fig:tax2}
  768. \end{figure*}
  769.  
  770. The second and third lines concern output. Only the prescence or
  771. absence of explicit attributes and timestamps are distinguished,
  772. leading to three categories. The last three lines concern valid-time
  773. selection (non-temporal selection is disregarded). Comparison
  774. operators may be duration-based or not; arguments be of either event,
  775. interval, or element type; and the arguments may or may not derive
  776. from valid times of tuples.
  777.  
  778. \section{The Benchmark Queries}
  779.  
  780. \subsection{Overview}
  781.  
  782. The structure of this section is based on Figure~\ref{fig:tax2}. There
  783. are three sections, each of which contains ten sections. The three
  784. top-level sections classify queries according to the output. Thus,
  785. the output from a query may have either only an explicit-attribute
  786. value component (O1), only a valid-time component (O2), or it may have
  787. both (O3).
  788.  
  789. Each top-level section contains the same ten sections. These divide
  790. queries based on a single, distinguished valid-time selection
  791. predicate\footnote{A query may contain several selection predicates,
  792.   but it is classified according to a single predicate.}. The
  793. predicate is of the format $arg_1$ {\tt op} $arg_2$ where {\tt op} is
  794. a comparison operator which may (or may not) be duration-based. One
  795. argument is the valid time of tuples in the argument relation. The
  796. other argument may be of event, interval, or element type;
  797. orthogonally, it may (or may not) be computed from existing valid
  798. times in the argument relation. This results in a total of ten
  799. classes (the combination of duration-based predicates and event
  800. arguments is omitted).
  801.  
  802. \begin{BNF}
  803. indentationindentat \= ionind \= \kill
  804. \> (S1) \> (Duration, Interval, Computed) \\
  805. \> (S2) \> (Duration, Interval, Other) \\
  806. \> (S3) \> (Duration, Element, Computed) \\
  807. \> (S4) \> (Duration, Element, Other) \\
  808. \> (S5) \> (Other, Event, Computed) \\
  809. \> (S6) \> (Other, Event, Other) \\
  810. \> (S7) \> (Other, Interval, Computed) \\
  811. \> (S8) \> (Other, Interval, Other) \\
  812. \> (S9) \> (Other, Element, Computed) \\
  813. \> (S10) \> (Other, Element, Other)
  814. \end{BNF}
  815.  
  816. \subsection{Explicit-attribute Output}
  817.  
  818. This section involves queries which return only explicit-attribute
  819. values---no valid-time values are present in the result.
  820.  
  821. \subsubsection{Class O1.S3 (Duration, Element, Computed)}
  822.  
  823. \query{Find the names of employees that have been in a department
  824.   named Toy for a shorter period than has DI.} 
  825.   {``Ed'' and ``Edward.''}
  826.   {(Projected, None) / (Duration, Element, Computed) / (=, Constant)
  827.     (=, Constant)}
  828.  
  829.   \noindent {\it The employee ED has been in a department named Toy
  830.     for a period which is shorter than that of DI. The categorization
  831.     is with respect to Figure 6. ``(Projected, None)'' indicates that
  832.     only part of the attributes of the argument relation are present
  833.     in the result and that there is no valid-time component. Next,
  834.     ``(Duration, Element, Computed)'' indicates that a duration based
  835.     predicates is used on element-valued arguments which are both
  836.     derived from the valid-times of stored facts.  Finally, ``(=,
  837.     Constant) (=, Constant)'' indicates that there are two
  838.     non-temporal selection predicates that test for equality of an
  839.     attribute value with a constant (i.e., the person must be DI and
  840.     the department must have name Toy).}
  841.  
  842. \query{Find the current name and department name for the persons which
  843.   made \$40K for a longer period than DI did.}
  844.   {``(Edward, Book).''}
  845.   {(Projected, None) / (Duration, Element, Computed) (Containment,
  846.     Event, Explicit) / (=, Constant)}
  847.  
  848.   \noindent {\it In this query, there are two valid-time selection
  849.     based predicates.  The one used for categorization compares the
  850.     duration of time when a person makes \$40K with the period of time
  851.     that DI makes \$40K. The other selects the name and department
  852.     that overlap with the current time of qualifying persons.}
  853.  
  854. \subsection{Valid-time Output}
  855.  
  856. This section involves queries which return only valid-time
  857. values---no explicit-attribute values are present in the result.
  858.  
  859. \subsection{Explicit-attribute and Valid-time Output}
  860.  
  861. The output from queries in this section contains explicit attribute
  862. values with associated valid times.
  863.  
  864. \end{document}